"""
遗传算法求解函数优化问题

问题描述：
    寻找函数 f(x) = x*sin(10πx)+2.0 在区间[-1, 2]上的全局最大值。
    该函数具有多个局部极值，传统优化方法容易陷入局部最优。

算法原理：
    使用遗传算法通过模拟自然选择和遗传过程来搜索最优解。
    - 编码方式：二进制编码，将自变量x编码为20位二进制串
    - 选择方法：轮盘赌选择，适应度高的个体被选中概率更大
    - 交叉操作：单点交叉，随机选择交叉点交换父代基因
    - 变异操作：随机位变异，以小概率翻转某些位的值

应用场景：
    函数优化问题广泛应用于工程设计、参数调优、机器学习等领域，
    特别适用于非凸、不可导或具有多个局部最优的复杂函数。

作者：斯黄
日期：2025年3月4日
"""

# 遗传算法求解函数 f(x) = x*sin(10πx)+2.0 在区间[-1, 2]的最大值
import numpy as np
import matplotlib.pyplot as plt

# 遗传算法参数
DNA_SIZE = 20         # DNA长度（二进制编码位数）
POP_SIZE = 100        # 种群规模
CROSS_RATE = 0.8      # 交叉概率
MUT_RATE = 0.003      # 变异概率
N_GENERATIONS = 100   # 迭代次数
X_BOUND = [-1, 2]     # 自变量范围

# 适应度函数
def F(x): return x * np.sin(10 * np.pi * x) + 2.0

# 二进制转十进制
def translateDNA(pop): 
    return pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / (2**DNA_SIZE-1) * (X_BOUND[1]-X_BOUND[0]) + X_BOUND[0]

# 计算适应度
def get_fitness(pred): return pred + 1e-3 - np.min(pred)

# 选择（轮盘赌）
def select(pop, fitness):
    idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True, p=fitness/fitness.sum())
    return pop[idx]

# 交叉
def crossover(parent, pop):
    if np.random.rand() < CROSS_RATE:
        i_ = np.random.randint(0, POP_SIZE, size=1)
        cross_points = np.random.randint(0, 2, DNA_SIZE).astype(np.bool)
        parent[cross_points] = pop[i_, cross_points]
    return parent

# 变异
def mutate(child):
    for point in range(DNA_SIZE):
        if np.random.rand() < MUT_RATE:
            child[point] = 1 if child[point] == 0 else 0
    return child

# 初始化种群
pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE))

# 在进化循环前添加：
plt.ion()
fig, ax = plt.subplots()
x = np.linspace(*X_BOUND, 200)
ax.plot(x, F(x))
sc = ax.scatter([], [], c='red')

# 进化过程
for _ in range(N_GENERATIONS):
    F_values = F(translateDNA(pop))
    fitness = get_fitness(F_values)
    pop = select(pop, fitness)
    pop_copy = pop.copy()
    for parent in pop:
        child = crossover(parent, pop_copy)
        child = mutate(child)
        parent[:] = child

    # 在进化循环内添加：
    ax.set_title(f'Generation {_}')
    sc.set_offsets(np.c_[translateDNA(pop), F_values])
    plt.pause(0.1)

# 输出结果
x = translateDNA(pop)
print("最大值点 x =", x[np.argmax(F(x))], "f(x) =", F(x).max())

# 在最后添加：
plt.ioff()
plt.show() 